翻訳と辞書 Words near each other ・ LKS Mackinnon Stakes ・ LKS Nieciecza ・ LKS Szubinianka Szubin ・ LKT (musician) ・ LKT Team Brandenburg ・ LKW-Maut ・ LKY ・ Lkáň ・ LL ・ Ll ・ LL chondrite ・ LL Cooke School Chicago ・ LL Cool J ・ LL Cool J discography ・ LL grammar ・ LL parser ・ LL postcode area ・ LL.M. U.S. Regulatory Trade Law ・ LL77 ・ LLA ・ LLA Azteca Championship ・ LLA Marker ・ Llacanora District ・ Llacao ・ Llach ・ Llacllin District ・ Llacuna (Barcelona Metro) ・ Lladorre ・ Lladró ・ Lladurs Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク LL parser ： ウィキペディア英語版 LL parser In computer science, an LL parser is a top-down parser for a subset of context-free languages. It parses the input from Left to right, performing Leftmost derivation of the sentence. An LL parser is called an LL(''k'') parser if it uses ''k'' tokens of lookahead when parsing a sentence. If such a parser exists for a certain grammar and it can parse sentences of this grammar without backtracking then it is called an LL(''k'') grammar. LL(''k'') grammars can generate more languages the higher the number ''k'' of lookahead tokens. A corollary of this is that not all context-free languages can be recognized by an LL(k) parser. An LL parser is called an LL('' *'') parser (an LL-regular parser) if it is not restricted to a finite ''k'' tokens of lookahead, but can make parsing decisions by recognizing whether the following tokens belong to a regular language (for example by means of a Deterministic Finite Automaton). LL grammars, particularly LL(1) grammars, are of great practical interest, as parsers for these grammars are easy to construct, and many computer languages are designed to be LL(1) for this reason. LL parsers are table-based parsers, similar to LR parsers. LL grammars can also be parsed by recursive descent parsers. == Overview == For a given context-free grammar, the parser attempts to find the leftmost derivation. Given an example grammar $G$: 1. $S\; \backslash to\; E$ 2. $E\; \backslash to\; (\; E\; +\; E\; )$ 3. $E\; \backslash to\; i$ the leftmost derivation for $w\; =\; ((i+i)+i)$ is: $S\backslash \; \backslash overset\backslash \; E\backslash \; \backslash overset\backslash \; (E+E)\backslash \; \backslash overset\backslash \; ((E+E)+E)\backslash \; \backslash overset\backslash \; ((i+E)+E)\backslash \; \backslash overset\backslash \; ((i+i)+E)\backslash \; \backslash overset\backslash \; ((i+i)+i)$ Generally, there are multiple possibilities when selecting a rule to expand given (leftmost) non-terminal. In the previous example of the leftmost derivation, in step 2: $S\backslash \; \backslash overset\backslash \; E\backslash \; \backslash overset\backslash \; ?$ We can choose from two rules: 2. $E\; \backslash to\; (\; E\; +\; E\; )$ 3. $E\; \backslash to\; i$ To be effective, the parser must be able to make this choice deterministically when possible, without backtracking. For some grammars, it can do this by peeking on the unread input (without reading). In our example, if the parser knows, that the next unread symbol is $($ the only correct rule that can be used is 2. Generally, $LL(k)$ parser can look ahead at $k$ symbols. However, given a grammar, the problem of determining if there exists a $LL(k)$ parser for some $k$ that recognizes it, is undecidable. For each $k$, there is a language that cannot be recognized by $LL(k)$ parser, but can be by $LL(k+1)$. We can use the above analysis to give the following formal definition: Let $G$ be a context-free grammar and $k\; \backslash ge\; 1$. We say that $G$ is $LL(k)$, if and only if for any two leftmost derivations: 1. $S\backslash \; \backslash Rightarrow\backslash \; \backslash dots\backslash \; \backslash Rightarrow\backslash \; wA\backslash alpha\backslash \; \backslash Rightarrow\backslash \; \backslash dots\backslash \; \backslash Rightarrow\backslash \; w\backslash beta\backslash alpha\backslash \; \backslash Rightarrow\backslash \; \backslash dots\backslash \; \backslash Rightarrow\backslash \; wx$ 2. $S\backslash \; \backslash Rightarrow\backslash \; \backslash dots\backslash \; \backslash Rightarrow\backslash \; wA\backslash alpha\backslash \; \backslash Rightarrow\backslash \; \backslash dots\backslash \; \backslash Rightarrow\backslash \; w\backslash gamma\backslash alpha\backslash \; \backslash Rightarrow\backslash \; \backslash dots\backslash \; \backslash Rightarrow\backslash \; wy$ Following condition holds: Prefix of the string $x$ of length $k$ equals the prefix of the $y$ of length $k$ implies $\backslash beta\backslash \; =\backslash \; \backslash gamma$. In this definition, $S$ is the starting and $A$ any non-terminal. The already derived input $w$, and yet unread $x$ and $y$ are strings of terminals. The greek letters $\backslash alpha$, $\backslash beta$ and $\backslash gamma$ represent any string of both terminals and non-terminals (possibly empty). The prefix length corresponds to the lookahead buffer size, and the definition says that this buffer is enough to distinguish between any two derivations of different words. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「LL parser」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.